package learn_0329;

import java.util.ArrayList;
import java.util.List;

public class 求和 {

    static List<List<Integer>> res = new ArrayList();

        public static int findTargetSumWays(int[] nums, int target) {
            List<Integer> track = new ArrayList();
            boolean[] visited = new boolean[nums.length];
            huisu(nums,visited,track,target,0);
            return res.size();
        }

    static void  huisu(int[] nums,boolean[] visited,List<Integer> track,int target,int sum){
            if(track.size()==nums.length){
                if(sum == target){
                    res.add(new ArrayList(track));
                }else{
                    return;
                }
            }
            for(int i=0;i<nums.length;i++){

                if(visited[i]){
                    continue;
                }

                sum += nums[i];
                visited[i] = true;
                track.add(nums[i]);
                huisu(nums,visited,track,target,sum);
                // 撤销选择1
                sum -= nums[i];
                 visited[i] = false;
                 track.remove(track.size()-1);
                // 选择2：减当前数字
                sum -= nums[i];
                 visited[i] = true;
                 track.add(nums[i]);
                huisu(nums,visited,track, target,sum);
                // 撤销选择2
                sum += nums[i];
                visited[i] = false;
                track.remove(track.size()-1);

            }
        }

    public static void main(String[] args) {
            int[] nums = {1,1,1,1,1};
            int target = 3;
            findTargetSumWays(nums,target);
            System.out.print("ok");
    }
}
